#include<iostream>
#include<vector>
#include<string>
#include<unordered_map>
using namespace std;


class Solution {
public:
    string minWindow(string s, string t) {
        unordered_map<char, int> hashMap;
        int totalCount = t.size();
        for (auto e : t) {
            hashMap[e]++;
        }
        int left = 0;
        int right = 0;
        int tmpCount = 0;
        int sLen = s.size();
        int ansl = 0;
        int ansr = INT_MAX;
        unordered_map<char, int> hashMapTmp;
        while (left < sLen) {
            while (right < sLen && tmpCount < totalCount) {
                if (hashMap.count(s[right])) {
                    if (hashMap.count(s[right]) &&
                        hashMap[s[right]] > hashMapTmp[s[right]]) {
                        tmpCount++;
                    }
                    hashMapTmp[s[right]]++;
                }
                right++;
            }
            while (left < sLen) {
                if (hashMap.count(s[left])) {
                    if (hashMap.count(s[left]) &&
                        hashMap[s[left]] == hashMapTmp[s[left]]) {
                        break;
                    }
                    hashMapTmp[s[left]]--;
                }
                left++;
            }
            // for (auto e : hashMap) {
            //     if (e.second > hashMapTmp[e.first]) {
            //         return ansr - ansl == INT_MAX ? ""
            //                                       : s.substr(ansl, ansr -
            //                                       ansl);
            //     }
            // }
            if (tmpCount < totalCount) {
                return ansr - ansl == INT_MAX ? ""
                    : s.substr(ansl, ansr - ansl);
            }
            if (ansr - ansl > right - left) {
                ansr = right;
                ansl = left;
            }
            if (left < sLen) {
                if (hashMap.count(s[left]) &&
                    hashMap[s[left]] <= hashMapTmp[s[left]]) {
                    hashMapTmp[s[left]]--;
                    tmpCount--;
                }
                left++;
            }
        }
        return ansr - ansl == INT_MAX ? "" : s.substr(ansl, ansr - ansl);
    }
};